package bit;

import java.io.*;
import java.util.Arrays;

/**
 * @author ZJX
 * @version 1.0
 * @descption
 * @since 2025/11/20 21:33
 */
public class Day29 {
//    public static void main(String[] args) throws IOException {
//        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
//        PrintWriter out = new PrintWriter(System.out);
//        in.nextToken();
//        int T = (int) in.nval;
//        while (T-- > 0) {
//            in.nextToken();
//            int H = (int) in.nval;
//            int count = 1;
//            int sum = 1;
//            int pre = 1;
//            while (sum != H) {
//                int remain = H - sum;
//                int doublePre = 2 * pre;
//                if (remain >= doublePre && remain % doublePre == 0) {
//                    sum += doublePre;
//                    pre = doublePre;
//                } else {
//                    sum += pre;
//                }
//            }
//            out.println(count);
//        }
//        out.close();
//    }

//    public static void main(String[] args) throws IOException {
//        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
//        PrintWriter out = new PrintWriter(System.out);
//        in.nextToken();
//        int n = (int) in.nval;
//        int[] nums = new int[n];
//        for (int i = 0; i < n; i++) {
//            in.nextToken();
//            nums[i] = (int) in.nval;
//        }
//        if (n == 1) {
//            out.println(1);
//            out.close();
//            return;
//        }
//        int i = 1;
//        int count = 1;
//        while (i < n) {
//            while (i < n && nums[i] == nums[i - 1]) {
//                i++;
//            }
//            if (i >= n) {
//                break;
//            }
//            if (nums[i] >= nums[i - 1]) {
//                // 递增区间
//                while (i < n && nums[i] >= nums[i - 1]) {
//                    i++;
//                }
//            } else {
//                while (i < n && nums[i] <= nums[i - 1]) {
//                    i++;
//                }
//            }
////            只有还有剩余元素，才需要新增子串
//            if (i < n) {
//                count++;
//            }
//        }
//        out.println(count);
//        out.close();
//    }

    /**
     * 最长严格上升子序列  -  动态规划
     *
     * @param nums int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];  // dp[i] 以i位置为结尾的最长严格上升子序列
        Arrays.fill(dp, 1);
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }

    /**
     * 最长严格上升子序列   - 贪心+二分解法
     *
     * @param nums int整型一维数组 给定的数组
     * @return int整型
     */
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] tail = new int[n];
        int len = 0;
        for (int num : nums) {
            int left = 0, right = len;
            while (right > left) {
                int mid = left + (right - left) / 2;
                if (tail[mid] >= num) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            tail[left] = num; // 优化末尾长度数组的值
            if (left == len) {
                len++;
            }
        }
        return len;
    }
}

